package 力扣链表;

import java.util.HashSet;
import java.util.Set;

public class Leedcode142环形链表 {
    public static void main(String[] args) {
        ListNode node4 = new ListNode(4,null);
        ListNode node3 = new ListNode(3,node4);
        ListNode node2 = new ListNode(2,node3);
        ListNode node1 = new ListNode(1,node2);
        node4.next = node2;
        detectCycle(node1);
    }
    //方法1：set去重
    public ListNode detectCycle1(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        int count = 0;
        while (head != null){
            if (set.contains(head)){
                return head;
            }
            set.add(head);
            head = head.next;
        }
        return null;
    }
    public static ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        do {
            if (slow != null && fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }else {
                return null;
            }
        }while (fast != slow);
        slow = head;
        while (slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
